package recursion

import (
	"math"
)

func MinStickers(stickers []string, target string) int {
	if stickers == nil || len(stickers) == 0 {return -1}
	stickersMap := make([][]int, len(stickers))
	for i:=0; i<len(stickers); i++ {
		stickersMap[i] = make([]int, 26)
		for _, s := range stickers[i] {
			stickersMap[i][s - 'a']++
		}
	}
	dp := map[string]int{}
	dp[""] = 0
	return MinStickersProcess(stickersMap, target, dp)
}

func MinStickersProcess(stickersMap [][]int, target string, dp map[string]int) int {
	if v, ok := dp[target]; ok {
		return v
	}
	ans := math.MaxInt64
	for i:=0; i<len(stickersMap); i++ {
		targetMap := make([]int, 26)
		for _, s := range target {
			targetMap[s - 'a']++
		}
		if stickersMap[i][GetFirstStr(targetMap)] == 0 {
			continue
		}
		for i, v := range stickersMap[i] {
			if targetMap[i] != 0 && targetMap[i] > v {
				targetMap[i] -= v
			} else if targetMap[i] != 0 && targetMap[i] <= v {
				targetMap[i] = 0
			}
		}
		tmp := MinStickersProcess(stickersMap, GenerateStr(targetMap), dp)
		if tmp != -1 {
			ans = Min(ans, 1+tmp)
		}
	}
	if ans == math.MaxInt64 {
		return -1
	}
	dp[target] = ans
	if v, ok := dp[target]; ok {
		return v
	}
	return ans
}

func GetFirstStr(targetMap []int) int {
	for i, v := range targetMap {
		if v != 0 {
			return i
		}
	}
	return 0
}

func GenerateStr(targetMap []int) string {
	ans := ""
	for i, v := range targetMap {
		for j:=0; j < v; j++ {
			ans += string(byte(97 + i))
		}
	}
	return ans
}
